package graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Dijkstra（迪杰斯特拉算法）未使用二叉堆优化的版本
 * 算法时间复杂度为 O(n^2)
 */
public class DijkstraNormal_1117 {
    public static Map<Node<Integer>, Integer> dijkstra(Node<Integer> source) {
        // 存储源点到任意节点的最短距离
        Map<Node<Integer>, Integer> distanceMap = new HashMap<>();
        // 存储已经确定最短距离的点
        Set<Node<Integer>> markNodes = new HashSet<>();
        // 初始化源点到自己的最短距离
        distanceMap.put(source, 0);

        // 获取没有确定最短距离且距离源点最近的点
        Node<Integer> minNode = getUnmarkMinDistanceNode(distanceMap, markNodes);

        // 只要找不到minNode后，才会停止循环，最坏情况显然是源点可以到达所有节点，因此循环时间复杂度显然是 O(n)
        while (null != minNode) {
            Integer distance = distanceMap.get(minNode);
            // 当前节点的所有直接边进行松弛
            for (Edge<Integer> edge : minNode.nextEdges) {
                // if (distanceMap.containsKey(edge.to)) {
                //     // 在距离表中，判断经过当前边后距离是否更近，只有距离更近才需要更新
                //     distanceMap.put(edge.to, Math.min(distanceMap.get(edge.to), distance + edge.weight));
                // } else {
                //     // 不在距离表中，直接更新距离
                //     distanceMap.put(edge.to, distance + edge.weight);
                // }
                // 上面的代码可以简化为
                distanceMap.put(edge.to, Math.min(distanceMap.getOrDefault(edge.to, Integer.MAX_VALUE), distance + edge.weight));
            }
            markNodes.add(minNode);

            // 每次都是 O(n)
            minNode = getUnmarkMinDistanceNode(distanceMap, markNodes);
        }
        return distanceMap;
    }

    /**
     * 获取没有确定最短距离且距离源点最近的点
     * 由于整个distanceMap，随着循环distanceMap中节点会越来越多，取决于点数，因此该方法的时间复杂度为 O(n)
     *
     * @param distanceMap 距离表
     * @param markNodes   确定距离的点
     */
    private static Node<Integer> getUnmarkMinDistanceNode(Map<Node<Integer>, Integer> distanceMap, Set<Node<Integer>> markNodes) {
        Node<Integer> minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for (Map.Entry<Node<Integer>, Integer> entry : distanceMap.entrySet()) {
            if (!markNodes.contains(entry.getKey()) && entry.getValue() < minDistance) {
                minNode = entry.getKey();
                minDistance = entry.getValue();
            }
        }
        return minNode;
    }
}
